nLab Möbius inversion

Idea

The classical Möbius inversion formula is a principle originating in number theory, which says that if $f$ and $g$ are two (say, complex-valued) functions on the positive natural numbers, then

$$f(n) = \sum_{d\mid n} g(d)$$

if and only if

$$g(n) = \sum_{d\mid n} f(d)\mu(n/d)$$

where the sums run over the divisors of $n$, and where $\mu$ is the Möbius function:

$$\mu(n) = \begin{cases}(-1)^r & n\,\text{ is the product of }\,r\,\text{ distinct primes}\\0 & \text{otherwise}\end{cases}$$

Gian-Carlo Rota(1964) described a vast generalization of the Möbius inversion formula, which was at the same time a generalization of the classical inclusion-exclusion principle in combinatorics. Rota’s formulation of Möbius inversion applies to functions defined over partially ordered sets, while further category-theoretic generalizations have also been proposed.

Möbius inversion for posets

Incidence algebras and the zeta function

The incidence algebra of a poset $P$ (relative to a commutative ring $R$) is an associative unital algebra defined as follows. Its elements are functions $f : P \times P\to R$ such that $x \nleq y$ implies $f(x,y) = 0$. Pointwise addition $f+g$ and scalar multiplication $r\cdot f$ are defined straightforwardly ($(f+g)(x,y) = f(x,y) + g(x,y)$, $(r\cdot f)(x,y) = r\cdot f(x,y)$), while the convolution product $f*g$ is defined as follows:

$$(f*g)(x,y) = \sum_{x \le z \le y} f(x,z) \cdot g(z,y)$$

Note that the unit of the convolution product is the Kronecker delta:

$$\delta(x,y) = \begin{cases}1 & x = y \\ 0 & \text{otherwise}\end{cases}$$

We write $I(P)$ for the incidence algebra of $P$. A special and important element of $I(P)$ is given by

$$\zeta(x,y) = \begin{cases}1 & x \le y \\ 0 & \text{otherwise}\end{cases}$$

referred to as the zeta function of $P$.

The Möbius function and the Möbius inversion formula

A Möbius function of $P$ is defined as an inverse to the zeta function with respect to the convolution product. Such an inverse always exists if the poset is locally finite, that is, if every interval $[x,y] = \{z \mid x \le z\le y\}$ is finite.

Proposition

(Rota 1964): If $P$ is a locally finite poset, then there exists a function $\mu$ such that $\zeta * \mu = \mu * \zeta = \delta$.

Proof

$\mu(x,y)$ can be computed by induction on the number of elements in the interval $[x,y]$. In the base case we set $\mu(x,x) = 1$. Otherwise in the case that $x \ne y$, we assume by induction that $\mu(x,z)$ has already been defined for all $z$ in the half-open interval $[x,y)$, and set

$$\mu(x,y) = -\sum_{x \le z \lt y} \mu(x,z).$$

From this definition, it is immediate that if

$$x_0 \lt x_1 \lt \cdots \lt x_n$$

is a chain of length $n$ in $P$, where each $x_{i+1}$ covers $x_i$, then for all $i \leq j$,

$$\mu(x_i,x_j) = \begin{cases}1 & i = j \\ -1 & j - i = 1\\ 0 & j - i \ge 2\end{cases}$$

It follows that both of the sums $\sum_{x \le z \le y} \mu(x,z)$ and $\sum_{x \le z \le y} \mu(z,y)$ add to zero unless $x = y$, hence that $\zeta*\mu = \mu*\zeta = \delta$.

We are now ready to state the Möbius inversion formula(s) for posets.

Proposition

(Rota 1964): Let $f$ and $g$ be functions defined over a locally finite poset $P$. Then

$$f(y) = \sum_{x \le y} g(x) \qquad\text{if and only if}\qquad g(y) = \sum_{x \le y} f(x)\mu(x,y).$$

Dually, we also have that

$$f(x) = \sum_{y \ge x} g(y) \qquad\text{if and only if}\qquad g(x) = \sum_{y \ge x} \mu(x,y)f(y).$$

Proof

An easy way of proving the Möbius inversion formulas (Kung et al.) is to view $\zeta$ and $\mu$ as matrices acting on the column vectors $f$ and $g$ by multiplication. Then the first proposition simply says that $f = g * \zeta$ iff $f * \mu = g$, while the dual formulation says that $f = \zeta * g$ iff $\mu * f = g$.

Properties of the Möbius function

Duality

The opposite poset $P^{op}$ has the same Möbius function as $P$ except with the arguments exchanged:

$$\mu_{P^{op}}(x,y) = \mu_P(y,x)$$

The product formula

The Möbius function of the cartesian product $P \times Q$ of two posets $P$ and $Q$ is the product of their Möbius functions:

$$\mu_{P\times Q}((x,y), (x',y')) = \mu_P(x,x') \cdot \mu_Q(y,y')$$

for all $x,x' \in P$ and $y,y' \in Q$.

The Galois coconnection theorem

Suppose $P$ and $Q$ are related by an adjunction (i.e., covariant Galois connection) $f \dashv g : Q \to P$. Then for all $x \in P$, $y \in Q$, the following equation holds:

$$\sum_{\substack{u \in P\\ f(u) = y}} \mu_P(x,u) = \sum_{\substack{v \in Q \\ g(v) = x}} \mu_Q(v,y)$$

(This result essentially goes back to Rota (1964) but in a slightly different formulation; for the above formulation, see Greene (1981), Aguiar and Ferrer Santos (2000), Kung et al. (2009).)

Examples of Möbius inversion

Inclusion-exclusion

Let $\mathcal{P}X$ be the lattice of subsets of a finite set $X$. $\mathcal{P}X$ is isomorphic to the cartesian product of $|X|$ many copies of $\mathbf{2} = \{ 0 \lt 1 \}$, and so by the product rule for the Möbius function, we have

$$\mu(I,J) = (-1)^{|J|-|I|}$$

for any pair of subsets $I,J \subseteq X$ such that $I \subseteq J$. The Möbius inversion formula then says that for any functions $f$ and $g$ defined on $\mathcal{P}X$, we have

$$f(J) = \sum_{I \subseteq J} g(I) \qquad\text{if and only if}\qquad g(J) = \sum_{I \subseteq J} (-1)^{|J|-|I|} f(I)$$

or dually that

$$f(I) = \sum_{J \supseteq I} g(J) \qquad\text{if and only if}\qquad g(I) = \sum_{J \supseteq I} (-1)^{|J|-|I|} f(J)$$

This is called the inclusion-exclusion principle.

As a textbook example of the inclusion-exclusion principle in action, suppose we want to compute $g(I)$ = the number of permutations of $X$ fixing exactly the elements in $I$. Well, it is easy to compute the number of permutations of $X$ fixing at least the elements in $I$,

$$f(I) = \sum_{J \supseteq I} g(J) = (|X|-|I|)!$$

but then we can compute $g$ in terms of $f$ via Möbius inversion. As a special case, when $|X| = n$ and $I = \emptyset$, we recover the classical formula for the number of derangements of $n$ elements:

$$!n = \sum_{k=0}^n (-1)^k \binom{n}{k} (n-k)! = \sum_{k=0}^n (-1)^k \frac{n!}{k!}$$

where a derangement is defined as a permutation fixing no elements.

Exercise: Prove that $n! = \sum_{k=0}^n (-1)^k \binom{n}{k} (n-k)^n$.

Number-theoretic Möbius inversion

The classical Möbius inversion formula is recovered by considering the set of positive natural numbers ordered by divisibility.

Möbius inversion for categories

Related concepts

• Euler characteristic
• incidence algebra
• inclusion-exclusion
• zeta polynomial

References

The classical reference on Möbius inversion for posets is:

• Gian-Carlo Rota, On the foundations of combinatorial theory I: theory of Möbius functions , Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 2 (1964), 340–368.

and a more modern reference is:

• Joseph P. S. Kung, Gian-Carlo Rota, Catherine H. Yan. Combinatorics: The Rota Way. Cambridge, 2009.

Möbius inversion for categories is discussed in:

• Tom Leinster, Notions of Möbius inversion, Bulletin of the Belgian Mathematical Society 19 (2012) 911-935, arXiv:1201.0413v3

• $n$Cafe: Möbius inversion for categories

Other references include:

• Curtis Greene, The Möbius Function of a Partially Ordered Set, NATO Advanced Study Institute, Series C (1981), 555-581.

• Joachim Kock, Incidence Hopf algebras, pdf

• Imma Gálvez-Carrillo, Joachim Kock, Andrew Tonks, Decomposition spaces, incidence algebras and Möbius inversion, arxiv/1404.3202

• Metropolis, N.; Rota, Gian-Carlo, Witt vectors and the algebra of necklaces, Advances in Mathematics 50 (2): 95–125 (1983) doi

• Marcelo Aguiar and Walter Ferrer Santos, Galois connections for incidence Hopf algebras of partially ordered sets, Adv. Math. 151 (2000), 71-100.

• wikipedia Möbius function, necklace polynomial

category: combinatorics